home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / awe2-0_1.lha / awe2-0.1 / Src / RCS / GenericFifo.cc,v < prev    next >
Text File  |  1989-02-21  |  6KB  |  336 lines
  1. head     3.2;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    grunwald:3.2; strict;
  6. comment  @@;
  7.  
  8.  
  9. 3.2
  10. date     89.02.20.15.34.39;  author grunwald;  state Exp;
  11. branches ;
  12. next     3.1;
  13.  
  14. 3.1
  15. date     88.12.20.13.48.45;  author grunwald;  state Exp;
  16. branches ;
  17. next     1.2;
  18.  
  19. 1.2
  20. date     88.10.30.13.04.27;  author grunwald;  state Exp;
  21. branches ;
  22. next     1.1;
  23.  
  24. 1.1
  25. date     88.09.18.16.42.21;  author grunwald;  state Exp;
  26. branches ;
  27. next     ;
  28.  
  29.  
  30. desc
  31. @@
  32.  
  33.  
  34. 3.2
  35. log
  36. @Start using Gnu library heaps for schedulers
  37. @
  38. text
  39. @// This may look like C code, but it is really -*- C++ -*-
  40. // 
  41. // Copyright (C) 1988 University of Illinois, Urbana, Illinois
  42. //
  43. // written by Dirk Grunwald (grunwald@@cs.uiuc.edu)
  44. //
  45. #include "stream.h"
  46. #include "Generic.h"
  47. #include "assert.h"
  48. //
  49. //    GenericFifo: A FIFO scheduler which uses a (fast) circular list
  50. //    to record threads.
  51. //
  52. //    voids are kept in the list. listHead is the index of the
  53. //    next thread to be removed. listTail is the index of the next
  54. //    *free slot*. 
  55. //
  56. //    To search the list, you start at listHead and move towards listTail,
  57. //    skipping over invalidated items.
  58. //
  59. //    when listElements == 0, the queue is *empty*, but listElements
  60. //    can be 0 and we can still have items in the list, since we
  61. //    removed mid-list items by zeroing them.
  62. //
  63. //    Thus, listHead == listTail implies listElements == 0, but
  64. //    it's not an iff.
  65. //
  66. //    When the queue becomes too big for the current list, it is
  67. //    expanded & the existing entries are copied to the new queue.
  68. //
  69. //    If the queue becomes empty & is below some threashold, it
  70. //    is removed.
  71. // 
  72.  
  73. static const char *GENERIC2(FIFO_NAME,Name) = GENERIC_STRING(FIFO_NAME) ;
  74.  
  75. FIFO_NAME::~FIFO_NAME()
  76. {
  77.     if (allocatedSize > 0) {
  78.     delete list;
  79.     delete pValid;
  80.     }
  81. }
  82.  
  83. //
  84. //    makeRoom assumes that listElements, listHead & listTail have been
  85. //    set
  86. // 
  87. void
  88. FIFO_NAME::reSize(int howMuch)
  89. {
  90.     
  91.     //
  92.     //    We can't remove any items, so we must insure we'll have enough
  93.     //    for the existing elements.
  94.     // 
  95.     
  96.     if (howMuch > listElements) {
  97.     
  98.     GENERIC2(FIFO_NAME,Item) *p = new GENERIC2(FIFO_NAME,Item)[howMuch];
  99.     char *validP = new char[howMuch];
  100.  
  101.     assert2( p != 0 && validP != 0,
  102.         "Unable to lengthen FIFO");
  103.     
  104.     bzero((void *) p, sizeof(GENERIC2(FIFO_NAME,Item)) * howMuch);
  105.     bzero((void *) validP, sizeof(char) * howMuch);
  106.     
  107.     if (listElements > 0) {
  108.         
  109.         //
  110.         //    Move over old list contents, taking care to compress the null
  111.         //    entries.
  112.         // 
  113.         
  114.         if (list == 0) {
  115.         cerr << "[" << GENERIC2(FIFO_NAME,Name) << "::makeRoom] null list found?\n";
  116.         exit(1);
  117.         }
  118.         
  119.         register GENERIC2(FIFO_NAME,Index) i;
  120.         register unsigned int moved;
  121.         for (i = listHead, moved = 0; moved < listElements;
  122.          i = advance(i)) {
  123.              if (pValid[i] != 0) {
  124.              p[moved] = list[i];
  125.              validP[moved] = 1;
  126.              moved++;
  127.              }
  128.          }
  129.         delete list;
  130.         delete pValid;
  131.     }
  132.     
  133.     list = p;
  134.     pValid = validP;
  135.     listTail = listElements;
  136.     listHead = 0;
  137.     allocatedSize = howMuch;
  138.     }
  139. }
  140.  
  141. void 
  142. FIFO_NAME::add(GENERIC2(FIFO_NAME,Item) *t) {
  143.     if (advance(listTail) == listHead 
  144.     || listElements >= allocatedSize)  {
  145.         reSize((allocatedSize <= 0)
  146.            ? 2
  147.            : ((allocatedSize * 3) / 2) );
  148.     }
  149.     list[listTail] = *t;
  150.     pValid[listTail] = 1;
  151.     listTail = advance(listTail);
  152.     listElements++;
  153. }
  154.  
  155. bool FIFO_NAME::remove(GENERIC2(FIFO_NAME,Item) *item) {
  156.     bool ok = TRUE;
  157.     if ((listElements > 0) && pValid[listHead]) {
  158.     *item = list[listHead];
  159.     pValid[listHead] = 0;
  160.     listHead = advance(listHead);
  161.     listElements--;
  162.     } else {
  163.     char valid = 0;
  164.     ok = TRUE;
  165.     do {
  166.         if (listHead == listTail || list == 0) {
  167.         ok = FALSE;
  168.         break;
  169.         }
  170.         *item = list[listHead];
  171.         valid = pValid[listHead];
  172.         pValid[listHead] = 0; // either 0 now, or make 0
  173.         listHead = advance(listHead);
  174.     } while(valid == 0);
  175.     if (ok) {
  176.         listElements--;
  177.     }
  178.     }
  179.     return(ok);
  180. }
  181.  
  182. bool FIFO_NAME::removeIfFound(GENERIC2(FIFO_NAME,Item)* toRemove) {
  183.     bool ok = TRUE;
  184.     if ((listElements > 0)
  185.     && pValid[listHead]
  186.     && list[listHead] == *toRemove) {
  187.         pValid[listHead]=0;
  188.         listHead = advance(listHead);
  189.         listElements--;
  190.     } else {
  191.         if (listElements == 0 || list == 0) {
  192.         ok = FALSE;
  193.         } else {
  194.         //
  195.         // check for common case -- head of list
  196.         //
  197.         bool valid = FALSE;
  198.         //
  199.         // make sure the validity of the item in the list
  200.         //
  201.         if (pValid[listHead] && list[listHead] == *toRemove) {
  202.             valid = TRUE;
  203.             pValid[listHead] = 0;
  204.             listHead = advance(listHead);
  205.             listElements--;
  206.         } else {
  207.             // 
  208.             //    Mid-list removal -- just nullify the pointer
  209.             //
  210.             register GENERIC2(FIFO_NAME,Index) i = listHead;
  211.             register unsigned int examined = 0;
  212.             //
  213.             // Set ok to FALSE. If we find the itme in the
  214.             // the list, we set ok to TRUE, indicating
  215.             // that it was deleted.
  216.             //
  217.             ok = FALSE;
  218.             while(examined < listElements) {
  219.             //
  220.             // If this is a valid item to consider...
  221.             //
  222.             if (pValid[i]) {
  223.                 examined++;
  224.                 if (list[i] == *toRemove) {
  225.                 ok = TRUE;
  226.                 pValid[i] = 0;
  227.                 listElements--;
  228.                 break;
  229.                 }
  230.             }
  231.             i = advance(i);
  232.             }
  233.         }
  234.         }
  235.     }
  236.     return(ok);
  237. }
  238.  
  239. bool
  240. FIFO_NAME::doStart(GENERIC2(FIFO_NAME,Index)& index,
  241.           GENERIC2(FIFO_NAME,Item)* item)
  242. {
  243.     index = listHead;
  244.     while (index != listTail) {
  245.     if (pValid[index]) {
  246.         *item = list[index];
  247.         return(1);
  248.     }
  249.     index++;
  250.     }
  251.     return(0);
  252. }
  253.  
  254. bool
  255. FIFO_NAME::doDelete(GENERIC2(FIFO_NAME,Index)& index)
  256. {
  257.     bool didDelete = 0;
  258.     if (pValid[index]) {
  259.     pValid[index] = 0;
  260.     listElements--;
  261.     didDelete = 1;
  262.     }
  263.     return(didDelete);
  264. }
  265.  
  266. bool
  267. FIFO_NAME::doNext(GENERIC2(FIFO_NAME,Index)& index,
  268.          GENERIC2(FIFO_NAME,Item)* item)
  269. {
  270.     bool gotOne = 0;
  271.     
  272.     if (index == listTail) return(0);
  273.     
  274.     index = advance(index);
  275.     
  276.     while (index != listTail) {
  277.     if (pValid[index]) {
  278.         *item = list[index];
  279.         return(1);
  280.     }
  281.     }
  282.     return(0);
  283. }
  284.  
  285. void
  286. FIFO_NAME::doDone()
  287. {
  288.     //
  289.     // Do nothing.
  290.     //
  291. }
  292.  
  293. bool
  294. FIFO_NAME::isEmpty()
  295. {
  296.     return( size() == 0);
  297. }
  298.  
  299. unsigned int
  300. FIFO_NAME::size()
  301. {
  302.     return(listElements);
  303. }
  304.  
  305. const char *FIFO_NAME::classIsA()
  306. {
  307.     return( GENERIC2(FIFO_NAME,Name) );
  308. }
  309. @
  310.  
  311.  
  312. 3.1
  313. log
  314. @Steay version
  315. @
  316. text
  317. @@
  318.  
  319.  
  320. 1.2
  321. log
  322. @*** empty log message ***
  323. @
  324. text
  325. @d211 1
  326. @
  327.  
  328.  
  329. 1.1
  330. log
  331. @Initial revision
  332. @
  333. text
  334. @d1 6
  335. @
  336.